斐波那契数列

2018.9.10 星期一 14:23

Fibonacci数列的数学表达式就是：
F(n) = F(n-1) + F(n-2)
F(1) = 1
F(2) = 1
0,1,1,2,3,5,8,13,21,34,55,89,144,233,…
0,1,2,3,4,5,6, 7, 8, 9,10,11, 12, 13,…

常见问题

### 1
1202年，义大利数学家斐波那契出版了他的“算盘全书”。他在书中提出了一个关于兔子繁殖的问题： 如果一对兔子每月能生一对小兔（一雄一雌），而每对小兔在它出生后的第三个月里，又能开始生一对小兔，假定在不发生死亡的情况下，由一对出生的小兔开始，50个月后会有多少对兔子？
### 2
假设你现在正在爬楼梯，楼梯有n级。每次你只能爬1级或者2级，那么你有多少种方法爬到楼梯的顶部？

15/n级楼梯，一步最多三级，爬上楼梯可以有多少种走法实现（js递归实现）
f(15) = f(14) + f(13) + f(12);

### 3
数列中相邻两项的前项比后项的极限是多少，就是问，当n趋于无穷大时，F(n)/F(n+1)的极限是多少？
答：这个可由它的通项公式直接得到，极限是(-1+√5)/2，这个就是所谓的黄金分割点，也是代表大自然的和谐的一个数字。

逻辑推理

### 兔子问题
根据 繁殖二叉树 可以直观的看到f(n)是f(n-1),f(n-2)两项的和
第n代 等于 (n-1)代的数量加上(n-1)代新生的数量；而新生兔的数量 是有生育能力的兔子的数量，也就是(n-2)代的兔子数量(需要生长/隔一个月 才可以生育)，(n-1)代并不是都有生育能力。

### 爬楼梯
爬n层楼梯的时候，可以考虑先前已经爬完的楼梯(n-1),(n-2),(n-3),…
最后一步 共有两种走法：1步 或者 2步；1步的走法f(n-1), 2步的走法f(n-2),即最后一步是确认的
同理 一步最多三级 的情况

1 1: 1
2 2: 11 2
3 3: 111 121 211
4 5: 1111 112 121 211 221
5 8: 11111 1112 1121 1211 122 2111 212 221
6 13:111111 …

算法

# 【算法】爬楼梯(JavaScript实现)

// 直接用不作处理的递归求解
const climbStairs = (n) => n < 3 ? n : climbStairs(n-1) + climbStairs(n-2) 
// 递推求解。
const climbStairs = (n) => {
  // 用一个数组保存每一次的结果
  let arr = new Array(n)
  for(let i = 1; i <= n; i++) {
    if(i < 3) {
      arr[i - 1] = i
    } else {
      // 逐一递推得到结果
      arr[i - 1] = arr[i - 2] + arr[i - 3]
    }
  }
  return n <= 0 ? 0 : arr[n - 1]
}
// $_迭代：用下面的改写:交换大小数/重新赋值数据
function climbStairs(n){
    var x1=x2=1;// 
    for(var i=1;i<n;i++){
        x2=x1+x2;
        x1=x2-x1;
    }
    return x2;
}

# 斐波那契数列算法分析

// 1 递归程序1：很直观的二叉递归程序  O（(3/2)^N）
long fib1(int n)
{
          if (n <= 2)
    {
            return 1;
    }
    else
    {
            return fib1(n-1) + fib1(n-2);
    }
}
// 2 递归程序2：用一叉递归程序就可以得到近似线性的效率
long fib(int n, long a, long b, int count)
{
     if (count == n)
         return b;
     return fib(n, b, a+b, ++count);
}
 long fib2(int n)
{
     return fib(n, 0, 1, 1);
}
// 3 迭代解法：O（N）
    // 也可以用数组将每次计算的f(n)存储下来，用来下次计算用（空间换时间）
long fib3 (int n)
{
     long x = 0, y = 1;
     for (int j = 1; j < n; j++)
     {
         y = x + y;
         x = y - x;
     }
     return y;
}
// 4 矩阵乘法：O（log(N)）
    // 显然用二分法来求，结合一些面向对象的概念，C++代码如下：
// 5 公式解法：
F(n)=

黄金分割比

黄金比率是源于神奇数字/菲波纳奇比率（Fibonnacci Number Sequence）。
黄金比率是由十三世纪末出生的义大利著名数学家斐波那契(Leonardo Fibonacci)发现的，比率由一组神奇数字计算而成。这串神奇数列，是任何相列的两个数字之和都等于后一个数字。即：1，1，2，3，5，8，13，21，34，55，89，144……如此类推。即1＋1＝2，1＋2＝3，2＋3＝5，3＋5＝8等。

(√5 – 1) / 2 ，一个约为 0.618 的无限不循环小数
# 为什么Fibonacci数列相邻两项之比会趋于0.618？
一个简单的解释就是，假设相邻两项之比存在一个极限，那么到了无穷远的时候，连续的三个数 a, b, a + b 将会满足 a / b = b / (a + b) ，这正好就是黄金比例的定义。

因而，不管数列的最初两个数是什么（比如说 2 和 7 ），只要今后每一个数都是前两个数之和，相邻两项之比总是会越来越接近 0.618 。这可以很好地解释一个我很喜欢的数学小魔术。

两杯浓度不同的盐水混合在一起，
a/b，另一杯盐水的浓度是 c/d，那么 (a+c)/(b+d) 一定介于 a/b 和 c/d 之间。
因此，(21a+34b)/(34a+55b) 就一定介于 21a/34a 和 34b/55b 之间。而 21a/34a = 21/34 ≈ 0.6176，34b/55b = 34/55 ≈ 0.6182，可见不管 a 和 b 是多少，(21a+34b)/(34a+55b) 都被夹在了 0.6176 和 0.6182 之间。如果 a 和 b 都不大，用 21a+34b 的值除以 0.618 来推测 34a+55b 是相当靠谱的。

其他

神奇的斐波那契数列
斐波那契数列为什么那么重要，所有关于数学的书几乎都会提到？

15:09

递归和迭代

[深究递归和迭代的区别、联系、优缺点及实例对比]

递归

递归的基本概念:程序调用自身的编程技巧称为递归,是函数自己调用自己.

使用递归要注意的有两点:
1)递归就是在过程或函数里面调用自身;
2)在使用递归时,必须有一个明确的递归结束条件,称为递归出口.

利用递归可以解决很多问题:如背包问题,汉诺塔问题,斐波那契数列…等.

由于递归引起一系列的函数调用,并且有可能会有一系列的重复计算,递归算法的执行效率相对较低.

迭代

迭代:利用变量的原值推算出变量的一个新值.如果递归是自己调用自己的话,迭代就是A不停的调用B.

递归空间消耗要比非递归代码要大很多，而且，如果递归深度太大，可能系统资源会不够用。

比较

二者关系
1） 递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换。
2） 能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出./相对/

往往有这样的观点：能不用递归就不用递归，递归都可以用迭代来代替。
万物的存在是需要时间的检验的，递归没有被历史所埋没，即有存在的理由。

从理论上说，所有的递归函数都可以转换为迭代函数，反之亦然，然而代价通常都是比较高的。但从算法结构来说，递归声明的结构并不总能够转换为迭代结构，
一个极典型的例子类似于链表，使用递归定义及其简单
采用递归算法需要的前提条件是，当且仅当一个存在预期的收敛时，才可采用递归算法，否则，就不能使用递归算法。

递归其实是方便了程序员难为了机器，递归可以通过数学公式很方便的转换为程序。其优点就是易理解，容易编程。
但递归是用栈机制实现的，每深入一层，都要占去一块栈数据区域，对嵌套层数深的一些算法，递归会力不从心，空间上会以内存崩溃而告终，而且递归也带来了大量的函数调用，这也有许多额外的时间开销。所以在深度大时，它的时空性就不好了。

而迭代虽然效率高，运行时间只因循环次数增加而增加，没什么额外开销，空间上也没有什么增加，但缺点就是不容易理解，编写复杂问题时困难

#include <iostream>
using namespace std;
 
//迭代实现斐波那契数列
long fab_iteration(int index)
{
	if(index == 1 || index == 2)
	{
		return 1;
	}
	else
	{
		long f1 = 1L;
		long f2 = 1L;
		long f3 = 0;
		for(int i = 0; i < index-2; i++)
		{   
			f3 = f1 + f2; //利用变量的原值推算出变量的一个新值
			f1 = f2;
			f2 = f3;
		}
		 return f3;
	}
}
 
//递归实现斐波那契数列
 long fab_recursion(int index)
 {    
	if(index == 1 || index == 2)
	{
		return 1;
	}
	else
	{
		return fab_recursion(index-1)+fab_recursion(index-2);    //递归求值
	}
}
 
int main(int argc, char* argv[])
{
	cout << fab_recursion(10) << endl;
	cout << fab_iteration(10) << endl;
	return 0;
}

遍历/枚举 等概念

递归(recursion)在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。

循环(loop)：指的是在满足条件的情况下，重复执行同一段代码。一般语言都会有三种类型的循环语句:for语句、while语句和do While语句。
可以理解为：循环就是迭代(重复)一些命令的代码块, 如果循环控制条件不满足的话, 就结束循环.

迭代（iterate），指的是按照某种顺序逐个访问列表中的每一项
可以理解为：遍历一个集合，把集合里的每个元素都遍历一边。有时候，迭代也会指循环执行，反复执行的意思。(这个迭是高潮迭起的迭！对迭代的理解有限，如果想详细了解，自己search！)

遍历（traversal），是树形结构的一种重要运算，指的是按照一定的规则访问树形结构中的每个节点，而且每个节点都只访问一次。
可以理解为：遍历，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。或者理解为按一定的次序系统地访问结构中的所有结点，使每个结点只被访问一次。

枚举(enumeration)，在数学和计算机科学理论中，一个集的枚举是列出某些有穷序列集的所有成员的程序，或者是一种特定类型对象的计数。这两种类型经常（但不总是）重叠。枚举是一个被命名的整型常数的集合！

# leetcode50 Pow(x, n)自定义实现指数运算
此处为题目链接

// 思路一：二分法计算
public double myPow(double x, int n) {
    if(x==0) return 0;
    if(n==0) return 1;
        
    x = n>0 ? x : 1/x;
    n = Math.abs(n);
    if(n%2!=0){
        return x*myPow(x, n-1);
    }
    long temp = 1;
    double result = x;
    while(n >= (temp+temp)){
        temp += temp;
        result *= result;
    }
    return result*myPow(x, n-(int)temp);
}
// 思路二：递归
double myPow(double x, int n) {
    if(n<0) return 1/x * myPow(1/x, -(n+1));
    if(n==0) return 1;
    if(n==2) return x*x;
    if(n%2==0) return myPow( myPow(x, n/2), 2);
    else return x*myPow( myPow(x, n/2), 2);
}